package code1.dp;

import java.util.Arrays;
import java.util.Collections;

/**
 * 原题链接：https://leetcode.cn/problems/partition-to-k-equal-sum-subsets/
 */
public class P698 {

    //状态压缩dp
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int n=nums.length;
        int sum= Arrays.stream(nums).sum();
        if(sum%k!=0){
            return false;
        }
        int p=sum/k;
        Arrays.sort(nums);
        if(nums[n-1]>p){
            return false;
        }
        boolean[] dp=new boolean[1<<n];     //dp[i]表示i的二进制所表示状态是否可行
        int[] curSum=new int[1<<n];         //curSum[i]表示i的二进制所表示状态的数字和
        dp[0]=true;
        for(int i=0;i<1<<n;i++){            //遍历所有的状态
            if(!dp[i]){
                continue;                   //该状态不行，直接跳过
            }
            for(int j=0;j<n;j++){           //遍历nums
                if(curSum[i]+nums[j]>p){
                    break;                  //当前状态加上nums[j]大于p,下个状态一定不满足
                }
                if(((i>>j) & 1)==0){            //当前状态不包含nums[j]
                    int next= i | (1<<j);       //下一个状态(加上nums[j]后的)
                    curSum[next]=(curSum[i]+nums[j])%p;
                    dp[next]=true;
                }
            }
        }
        return dp[(1 << n) - 1];
    }
}
